package org.hot100_6.leetcode160;

import org.algorithm.List.ListNode;

import java.util.HashSet;
import java.util.List;

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> hashSet = new HashSet<>();

        while (headB != null) {
            hashSet.add(headB);
            headB = headB.next;
        }

        while (headA != null) {
            if (hashSet.contains(headA)) {
                return headA;
            }

            headA = headA.next;
        }

        return null;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        int lengthA = 0;
        int lengthB = 0;

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != null) {
            pA = pA.next;
            lengthA++;
        }

        while (pB != null) {
            pB = pB.next;
            lengthB++;
        }
        pA = headA;
        pB = headB;

        if (lengthA > lengthB) {
            for (int i = 0; i < lengthA - lengthB; i++) {
                pA = pA.next;
            }
        } else {
            for (int i = 0; i < lengthB - lengthA; i++) {
                pB = pB.next;
            }
        }


        while (pA != null) {
            if (pA == pB) {
                return pA;
            }

            pA = pA.next;
            pB = pB.next;
        }

        return null;
    }
}
